package study.算法Algorithm.排序算法.希尔排序;

import java.util.Arrays;

/*
    希尔排序交换法
 */
public class ShellSort {

    /*

     */
    public static void main(String[] args) {
        m01();
        m02();

    }

    private static void m02() {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if (arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "轮后=" + Arrays.toString(arr));
        }
    }

    private static void m01() {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int temp = 0;
        int count = 0;
        //循环的轮次
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //这里之所以循环总长度-gap次是因为，倒数gap那几个数后面已经没有数了
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "轮后=" + Arrays.toString(arr));
        }
    }
}
